package codeTop;

import java.util.*;

public class q199 {
    //dfs
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root,list,0);
        return list;
    }
    void dfs(TreeNode node,List<Integer> list,int depth){
        if (node == null) {
            return;
        }
        if (list.size() == depth) {
            list.add(node.val);
        }
        dfs(node.right,list,depth+1);
        dfs(node.left,list,depth+1);
    }
    //bfs
    public List<Integer> rightSideView1(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size -1; i++) {
                TreeNode poll = queue.poll();
                if (poll.left!=null) queue.add(poll.left);
                if (poll.right!=null) queue.add(poll.right);
            }
            TreeNode poll = queue.poll();
            if (poll.left!=null) queue.add(poll.left);
            if (poll.right!=null) queue.add(poll.right);
            list.add(poll.val);
        }
        return list;
    }
}
